package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * description:
 * author:zt
 * date:2024-09-07
 */


public class leetcode589 {

    /**
     * leetcode589
     * 给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。
     *
     * n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
     */
    public List<Integer> preorder(Node root) {
        if (root == null) return Collections.emptyList();
        return solveNode(root);
    }


    /**
     * leetcode 590
     * 给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
     *
     * n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
     */
    public List<Integer> postorder(Node root) {
        if (root == null) return Collections.emptyList();
        return solvePostOrder(root);
    }

    private List<Integer> solvePostOrder(Node root) {
        if (root.children.isEmpty()) {
            return Collections.singletonList(root.val);
        }
        List<Integer> res = new ArrayList<>();

        root.children.forEach(c -> res.addAll(solvePostOrder(c)));
        res.add(root.val);
        return res;
    }


    private List<Integer> solveNode(Node root) {
        if (root.children.isEmpty()) {
            return Collections.singletonList(root.val);
        }
        List<Integer> res = new ArrayList<>();
        res.add(root.val);
        root.children.forEach(c -> res.addAll(solveNode(c)));
        return res;
    }
}


    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
}
